package LeetCode_力扣;

//21. 合并两个有序链表
//要求：将两个升序链表合并为一个新的 升序 链表并返回。
// 新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 *思路一： 要求新链表是原链表拼接而成，说明这里不允许创建新节点。
 *  搞一个虚拟节点dummyHead，然后用prve引用连接正确的一次然后，
 *  向后移。 如果有一个走到空要记得连接另一个
 */

/*

public class mergeTwoLists_21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode dummyHead  = new ListNode();//虚拟头节点
        ListNode prve = dummyHead;//用来指向正确的方法

        //判空
        if( list1 == null ){
            return list2;
        }

        if(list2 == null){
            return list1;
        }

        while(list1 != null || list2 != null){

            if(list1.val <= list2.val){
                prve.next = list1;
                list1 = list1.next;//后移
            }else{
                prve.next = list2;
                list2 = list2.next;//后移
            }

            prve = prve.next;//后移
        }

        //判空
        if( list1 == null ){
            prve.next = list2;
        }

        if(list2 == null){
            prve.next = list1;
        }

        return dummyHead.next;
    }
}

 */


/**
 * 思路二：递归法。 每次只判断头节点的大小，剩下的交给子方法去处理，并返回地址
 */

/*

public class mergeTwoLists_21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        //终止条件
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }

        if(list1.val <= list2.val){

            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }

        list2.next = mergeTwoLists(list1, list2.next);
        return list2;

    }
}

 */











/*

public class mergeTwoLists_21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    }
}

 */




//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode() {
//    }
//
//    ListNode(int val) {
//        this.val = val;
//    }
//
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}
